// 双指针法
// 最优解：O(n + m)，其中n和m是两个数组的长度
// 空间复杂度：O(n + m)，需要额外空间存储合并后的数组


function mergeSortedArrays(arr1, arr2) {
  const merged = [];
  let i = 0; // arr1的指针
  let j = 0; // arr2的指针

  // 遍历两个数组，比较当前元素大小
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      merged.push(arr1[i]);
      i++;
    } else {
      merged.push(arr2[j]);
      j++;
    }
  }

  // 将剩余元素添加到结果数组
  while (i < arr1.length) {
    merged.push(arr1[i]);
    i++;
  }

  while (j < arr2.length) {
    merged.push(arr2[j]);
    j++;
  }

  return merged;
}

// 使用示例
const arr1 = [1, 3, 5, 7];
const arr2 = [2, 4, 6, 8];
console.log(mergeSortedArrays(arr1, arr2)); // [1, 2, 3, 4, 5, 6, 7, 8]